package com.itheima.mysort;

public class A03_InsertDemo1 {
    public static void main(String[] args) {
        //插入排序

        int[] arr = {1, 2, 4, 7, 7, 7, 5, 8, 9, 6};

        //先将数据分成有序无序两部分，再将无序数据依次插入有序
        //第一个无序对应的索引是1，从索引1开始和前面比较插入
        //怎么找到这个1
        //获取无序索引
        int index = getIndex(arr);
        System.out.println(index);


        //外循环：拿到每一个无序的数据
        for (int i = index; i < arr.length; i++) {
            //内循环：遍历有序数据，拿外循环得到的无序数据和每一个有序数据作比较
//            for (int j = 0; j < i; j++) {
//                //判断
//                if(arr[i]<arr[j]){
//                    int temp = arr[j];
//                    arr[j]= arr[i];
//                    arr[i] = temp;
//                }

            //下面的方法更好
            int j = i;

            while (j > 0 && arr[i] < arr[i - 1]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                i--;
            }

        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    private static int getIndex(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //判断
            if (arr[i] > arr[i + 1]) {
                //无序
                return i + 1;
            }
        }
        return -1;
    }
}
